package course.p8_NTree;


/**
 * N叉树结构: 这里实现四叉树结构
 */
public class NTree {
    //根节点
    private Node root;
    //树大小
    private int size;
    //树节点状态图
    private Node[][] stateCollect;

    /**
     * 定义四叉树的层数新建二叉树
     * @param n 层数
     */
    public NTree(int n){
        root = new Node();
        initStateCollect(n);
    }

    /**
     * 初始化树节点状态图
     */
    void initStateCollect(int n) {
        stateCollect = new Node[n][];
        stateCollect[0] = new Node[1];
        for(int i=0;i<stateCollect.length-1;i++){
            stateCollect[i+1] = new Node[4<<(i<<1)];
        }
    }

    /**
     * 按层次进行节点添加
     * @param data
     */
    public void add(Integer data){
        if(root.getData()==null){
            root.setData(data);
            stateCollect[0][0] = root;
            size = 1;
        }else{
            //首先找到最近的空余位置
            int col = 0,row = 0;
            for(int i=0;i<stateCollect.length;i++){
                Node[] state = stateCollect[i];
                for(int j=0;j<state.length;j++){
                    if(state[j]==null){
                        col = i;
                        row = j;
                        break;
                    }
                }
                if(col>0) break;
            }
            //将新节点添加到空余位置中
            stateCollect[col][row] = new Node(data);
            //将节点之间的关系维护到树结构中
            Node pri;
            if(row%4==0){
                pri = stateCollect[col-1][row/4];
                pri.setFirstChild(stateCollect[col][row]);
            }else {
                pri = stateCollect[col][row-1];
                pri.setNextBother(stateCollect[col][row]);
            }
            size++;
        }
    }

    /**
     * 四叉树遍历
     * @param type
     */
    public void Traverse(String type){
        normalTraverse(root);

    }

    /**
     * 普通递归遍历：根节点优先，兄弟节点其次，孩子节点最后
     * @param root 根节点
     */
    private void normalTraverse(Node root){
        if(root!=null){
            System.out.print(root.getData()+" ");
            normalTraverse(root.getNextBother());
            normalTraverse((root.getFirstChild()));
        }
    }

}
